/*
Given two sorted linked list, create a third list which contains only those elements of first list, which are not common with second list.
 Do this with O(n) time. Discuss all possible test cases for this function and whether your function can handle all those test cases.
*/

class Node
{
      public:
             int data;
             Node *next;
             Node(int value)
             {
                      data = value;
                      next = NULL;
             }
};
 // pseudo code
 void mergeList(Node *head1, Node *head2)
 {
      // head3 is the head node of the 3rd linked list
      Node *head3 = NULL;
      while(head1 != NULL && head2 != NULL)
      {
      // add the nodes in the 3rd list in the sorted order
            if(head1->data !=  head2->data)
            {
                 Node *newNode = new Node(0);        // create new dummy node
                 if(head1->data < head2->data)
                 {
                      newNode->data = head1->data;
                      head1 = head1->next;
                 }
                 else
                 {
                     newNode->data = head2->data;
                     head2 = head2->next;
                 }
                 // adds the newly created nodes in the 3rd linked list
                 if(!head3)
                      head3 = head3->next;
                 else
                     head3->next = newNode;
            }
      }
 }
